/**
 * 二分查找
 *
 */
// let A = [1, 90, 8, 12, 23, 105, 10, 26];
let A = [99, 25, 20, 19, 13, 10, 9, 6, 2];
// A = A.sort((a, b) => a - b);
console.log(A);
/** 
 * 设计函数，问题抽象
 * 设计一个函数bsearch有返回值，返回值为匹配元素的下标，没有匹配上就返回-1
 * arr:有序数组集合
 * searchVal:查找的元素
 * 传入的集合必须是有序集（升序或者降序）如果是乱序就需要进行排序后在进行传入。
 * 传入的有序集合是一个升序
 */
const bsearchAsc = (arr, searchVal) => {
	if (!arr.length) return -1;
	//l:左边开始的边界，r:右边开始是边界，guess:出现的位置
	let l = 0,
		r = arr.length - 1,
		guess;
	while (l <= r) {
		//设定比较的元素
		guess = Math.floor((l + r) / 2);
		if (arr[guess] == searchVal) {
			return guess;
		} else if (arr[guess] > searchVal) {
			//需要查找的值在当前值的前面
			r = guess - 1;
		} else {
			//需要查找的值在当前值的后面
			l = guess + 1;
		}
	}
	return -1;
}

/* 	
	降序的二分查找
	跟升序唯一不同的就是判断条件的不同
 */
const bsearchDesc = (arr, val) => {
	if (!arr.length) return -1;
	let l = 0,
		r = arr.length - 1,
		guess;
	while (l <= r) {
		guess = Math.floor((l + r) / 2);
		if (arr[guess] == val) {
			return guess;
		} else if (arr[guess] > val) {
			//当前值比查找值大,说明查找值在当前值的后面
			l = guess + 1
		} else {
			//当前值比查找值要小，说明查找值在当前值的前面
			r = guess - 1;
		}
	}
	return -1;
}

// console.log(bsearchAsc(A, 99))
console.log(bsearchDesc(A, 2))
